package Backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
* Offer38. 字符串的排列
*
* */
public class Offer38permutation {
    Set<String> res=new HashSet<>();
    public String[] permutation(String s) {
        boolean[] visited=new boolean[s.length()];
        backTrack(s,new StringBuffer(),visited);
        return res.toArray(new String[s.length()]);
    }

    private void backTrack(String s, StringBuffer sb,boolean[] visited) {
        if(sb.length()==s.length()){
            res.add(sb.toString());
            return;
        }
        for(int i=0;i<s.length();i++){
            if(visited[i]){
                continue;
            }
            visited[i]=true;
            sb.append(s.charAt(i));
            backTrack(s, sb, visited);
            sb.deleteCharAt(sb.length()-1);
            visited[i]=false;
        }
    }
}
